1. Field of the Invention
This invention relates to computer systems, and more particularly, to methods and apparatus for describing computer output images.
2. History of the Prior Art
In three dimensional graphics, surfaces are typically rendered by assembling a plurality of polygons in a desired shape. The polygons are conventionally triangles having vertices which are defined by three dimensional coordinates in world space, by color values, and by texture coordinates. Other characteristics such as transparency and additional textures may also define each vertex in a particular system to provide more sophisticated rendering. Such other characteristics may also be indexed and manipulated in accordance with the present invention. However, the description is limited to a smaller number of characteristics in order to help clarify the invention.
The surfaces represented by an assembly of polygons are, as a generality, being viewed in perspective. Consequently, the three dimensional world space coordinates are transformed into screen coordinates in which horizontal and vertical values (x, y) define screen position and a depth value z determines how near a vertex is to the screen and thus whether that vertex is viewed with respect to other points at the same screen coordinates. The color values define the brightness of each of red/green/blue (r, g, b) colors at each vertex and thus the color at each vertex. The texture coordinates (u, v) define the coordinates of each vertex on a texture map defined by values stored in memory.
The texture map describes a pattern to be applied to the surface of the triangle to vary the color in accordance with the pattern. The texture coordinates of the vertices of a triangular surface area define the position of the triangle on the texture map, the texture coordinates determine the texture applied to each portion of the surface within the triangle. In turn, the three dimensional coordinates of the vertices of a triangle positioned on the texture map define the plane in which the texture map and the surface lie with respect to the screen surface.
In order to provide the data to be stored in a frame buffer by which a triangle may be drawn on the two dimensional screen, the screen vertices of the particular triangle are first determined from the world three dimensional coordinates. Once the vertices of a triangle have been defined in screen space, the triangle is positioned in screen space so that all of the pixels defining that triangle are determined.
Since the original triangle lies in a plane in world space, the depth of its vertices vary linearly in world space from one to the other within the triangle. This allows the depth value for each position in the triangle to be determined in world space by a linear interpolation process. The depth of each pixel which defines the triangle projected onto the screen may be determined by perspective transformation using algorithms well known to those skilled in the art. Similarly, the color values and the texture coordinates for each pixel defining the triangle vary linearly from vertex to vertex in world space; and the same type of linear interpolation process in world space and perspective transformation back to screen space may be used to find the color values and texture coordinates for each pixel in screen space. Once the depth values, color values, and texture coordinates for each pixel have been determined in screen space, the texture coordinates are utilized to determine texture values from the texture map; and these texture values are utilized to modify the color values of each pixel in the triangle.
The texture coordinates u and v of each pixel provide an index into a map of texture values typically stored in memory which together describe a particular texture pattern that is to be applied in world space to the surface of the triangle. If a texture map describes a brick wall, for example, then a texture value may be derived using the u and v coordinates of the pixel which value reflects how the brick texture appears at that position on the texture map and the triangle. This texture value is then used to modify the r, g, b color values determined for that position on the triangle.
Since each individual screen pixel describing the triangle covers some portion of the texture map as it is projected onto the screen, each screen pixel will cover some one or more texture values on the projected triangle. Texture coordinates obtained by the interpolation and perspective transformation processes are not typically integer values. On the other hand, indexing into a texture map is accomplished using integral coordinates. Consequently, non-integral coordinates obtained by interpolation and perspective transformation must somehow be used for indexing to obtain texture values. A simple method of obtaining texture values uses the closest integral u and v values for each pixel to index into the texture map and selects the value at that intersection. A more accurate method of representing the texture pattern utilizes the integer portion of the u and v coordinates for each pixel to index into the texture map, and then uses the fractional portion in a process called bilinear interpolation to provide weighted amounts of the texture values (texels) in the texture map closest surrounding the central point reached by indexing. These fractional portions (typically the four values closest to this intersection) are combined and blended into a more accurate representation for modifying the pixel color values to reproduce the texture pattern.
Those skilled in the art have recognized that where a pixel covers a very large number of texture values on a texture map, only a small portion of those values will be represented in the texture value selected to modify the color of that pixel using the bilinear interpolation method. Consequently, a more accurate method of texture mapping has been devised. The method provides texture maps at a plurality of different scales so that the pixels defining the individual triangles may be made to cover relatively constant numbers of texels in the projection of the texture map in screen space. The process of selecting a texture value for a pixel then includes an initial step for each particular triangle being rendered in which a texture map is selected having a scale adapted to accurately represent texture values for the pixels of that triangle. By choosing the correct scale for the texture map relative to pixel size, a pixel on the screen may be made to cover only a few texels so that the texture values selected for combining to define a resulting texture value for each pixel provide a more faithful value than is possible using either of the simpler methods. The process is described in a paper entitled "Pyramidal Parametrics," presented at Siggraph proceedings, 1984.
In order to make the scale selection process more accurate, an additional process by which texture maps of the two closest scales to a desired pixel to texel size are selected are selected, and the texture values provided by those two different texture maps are interpolated to provide values closer to the desired scale.
Although these methods provide progressively more accurate forms of rendering pixels on the screen if the triangle lies in a plane parallel to the screen surface, each of these methods is based on the assumption that the projection of a pixel onto the texture map is square or rectangular in shape and aligned to the same axes as is the texture map. This assumption is incorrect in the greater number of cases when three dimensional shapes are being rendered. For example, these methods are less than representative if the vertices of the triangle being mapped are at significantly different depths so that pixels describing a scan line are warped and of different sizes when projected onto the triangle. In fact, none of these methods is capable of describing with sufficient accuracy the texture values which should be attributed to the pixels when three dimensional shapes are rendered in any significant perspective on a flat screen surface.
It is desirable to provide a method for more realistically mapping texture values to pixels representing three dimensional shapes than has been possible with prior art methods.